package com.ls.sort_algorithm;

import java.util.Arrays;
import java.util.Date;

/**
 * 基数排序(桶排序)
 * 这里没实现负数
 * 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
 */
public class RadixSort {
    public static void main(String[] args) {
        RadixSort radixSort = new RadixSort();
        int[] arr = {3, 7, -10,9, 11, 16, 10, 5, 1};

//        int[] arr = new int[800000];
//        for (int i = 0; i < 800000; i++) {
//            arr[i] = (int) (Math.random() * 8000000);
//        }

        System.out.println(new Date());
        radixSort.radixSort(arr);
        System.out.println(new Date());
        System.out.println(Arrays.toString(arr));
    }

    public void radixSort(int[] arr) {

        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();//知道了最大值是几位

        //定义一个二维数组,表示10个桶,每个桶就是一个移位数组
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中,实际存放了多少数据,我们定义一个一维数组
        int[] bucketElementCount = new int[10];

        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                int digitOfEle = arr[j] / n % 10; //取个位值
                bucket[digitOfEle][bucketElementCount[digitOfEle]] = arr[j];
                bucketElementCount[digitOfEle]++;
            }

            //按照桶的顺序,依次取出
            int index = 0;
            for (int k = 0; k < 10; k++) {
                //如果桶中有数据,则放入原来数组
                if (bucketElementCount[k] != 0) {
                    for (int l = 0; l < bucketElementCount[k]; l++) {
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                bucketElementCount[k] = 0;
            }
        }
    }


}
